//200. 岛屿数量
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m=grid.size(),n=grid[0].size();//m为行数，n为列数
        auto dfs=[&](this auto&dfs,int i,int j)->void{// lambda 表达式
        // 出界，或者不是 '1'，就不再往下递归
            if(i<0||i>=m||j<0||j>=n||grid[i][j]!='1'){
                return;
            }
            grid[i][j]='2';// 插旗！避免来回横跳无限递归
            dfs(i,j-1);// 往左走
            dfs(i,j+1);// 往右走
            dfs(i-1,j);// 往上走
            dfs(i+1,j);// 往下走
        };

        int ans=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'){// 找到了一个新的岛
                 dfs(i,j);// 把这个岛插满旗子，这样后面遍历到的 '1' 一定是新的岛
                 ans++;
                }
            }
        }
        return ans;
    }
};



//994. 腐烂的橘子
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int minute=0,fresh=0;
        queue<pair<int,int>>q;
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                if(grid[i][j]==1)fresh++;
                else if(grid[i][j]==2)q.push({i,j});
                }
            }
            vector<pair<int,int>>dirs={{-1,0},{1,0},{0,-1},{0,1}};
            while(!q.empty()){
                int n=q.size();
                bool rotted=false;//初始没腐烂
                for(int i=0;i<n;i++){
                    auto x=q.front();
                    q.pop();//用过，删除
                    //开始感染
                    for(auto cur:dirs){
                        int i=x.first+cur.first;
                        int j=x.second+cur.second;
                        if(0<=i&&i<grid.size()&& j >= 0&&j<grid[0].size()&&grid[i][j]==1 )                      {
                            grid[i][j]=2;
                            q.push({i,j});//加入新感染的坐标
                            fresh--;
                            rotted=true;//标记
                         }   
                    }
                 }
           if(rotted) minute++;
        }
        return fresh?-1:minute;
    //还有幸存未感染的，不算总时间
    }
};



// 207. 课程表
